import java.util.Arrays;

/**
 * @ClassName KP11_binarySearch
 * @Description: TODO
 * @Author: JCC
 * @CreateTime: 2023/10/9 9:18
 */
public class KP14_localMinimum {

    /**
     * 局部最小，相邻的数不相等
     *
     * @param rands
     * @return
     */
    public static int localMinimum(int[] rands) {
        if (rands == null || rands.length == 0) {
            return -1;
        }
        int len = rands.length;
        if (len == 1) return 0;
        // 最左端局部最小
        if (rands[0] < rands[1]) return 0;
        // 最右端局部最小
        if (rands[len - 2] > rands[len - 1]) return len - 1;
        int L = 0;
        int R = rands.length - 1;
        // 保持三个数可以比较
        while (L < R - 1) {
            int mid = (L + R) / 2;
            if (rands[mid - 1] > rands[mid] && rands[mid + 1] > rands[mid]) {
                return mid;
            } else if (rands[mid - 1] < rands[mid]) {
                R = mid - 1;
            } else {
                L = mid + 1;
            }
        }
        // 最后只剩两个数
        return rands[L] < rands[R] ? L : R;
    }

    /**
     * 检查查找算法是否正确
     */
    public static boolean check(int[] rands, int mid) {
       if (rands == null || rands.length == 0) {
           return false;
       }
       int left = mid-1;
       int right = mid + 1;
       boolean leftFlag = left >= 0 ? rands[left] > rands[mid] : true;
       boolean rightFlag = right < rands.length ? rands[right] > rands[mid] : true;
       return leftFlag && rightFlag;
    }

    /**
     * 生成任意规模的抽样测试数组
     * 相邻两数不相等
     * @param maxLen
     * @param maxValue
     * @return
     */
    public static int[] randomArray(int maxLen, int maxValue) {
        int[] rands = new int[(int) (Math.random() * (maxLen + 1))];
        int len = rands.length;
        if (len > 0) {
            rands[0] = (int) (Math.random() * (maxValue + 1) - Math.random() * maxValue);
            for (int i = 1; i < len; i++) {
                do {
                    rands[i] = (int) (Math.random() * (maxValue + 1) - Math.random() * maxValue);
                }while ((rands[i-1] == rands[i]));
            }
        }
        return rands;
    }

    /**
     * 生成测试查找函数
     */
    public static void testFind() {
        int maxLen = 10;
        int maxValue = 1000;
        int maxtimes = 100000;
        boolean flag = true;
        for (int i = 0; i < maxtimes; i++) {
            int[] rands = randomArray(maxLen, maxValue);
            if (rands == null || rands.length == 0) {
                System.out.println("数组为null或为空");
                continue;
            }
            int index = localMinimum(rands);
            if (!check(rands,index)) {
                System.out.println(Arrays.toString(rands));
                System.out.println(index);
                flag = false;
                break;
            }
            System.out.println("一组用例测试成功!!!");
        }
        System.out.println(flag ? "Congratulations Success!!!" : "Fatal error!!!");

    }

    public static void main(String[] args) {
        // 测试testFind函数
        testFind();
    }
}
